package com.shm.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 257. 二叉树的所有路径
 * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 示例:
 *
 * 输入:
 *
 *    1
 *  /   \
 * 2     3
 *  \
 *   5
 *
 * 输出: ["1->2->5", "1->3"]
 *
 * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
 *
 * @author SHM
 */
public class BinaryTreePaths {
    /**
     * 方法一：深度优先搜索
     * 思路与算法
     *
     * 最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。
     *
     * 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
     * 如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。
     * 如此，当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径。当然，深度优先搜索也可以使用非递归的方式实现，
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N^2)O(N
     * 2
     *  )，其中 NN 表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次会对 path 变量进行拷贝构造，时间代价为 O(N)O(N)，故时间复杂度为 O(N^2)O(N
     * 2
     *  )。
     *
     * 空间复杂度：O(N^2)O(N
     * 2
     *  )，其中 NN 表示节点数目。除答案数组外我们需要考虑递归调用的栈空间。在最坏情况下，当二叉树中每个节点只有一个孩子节点时，即整棵二叉树呈一个链状，此时递归的层数为 NN，此时每一层的 path 变量的空间代价的总和为 O(\sum_{i = 1}^{N} i) = O(N^2)O(∑
     * i=1
     * N
     * ​
     *  i)=O(N
     * 2
     *  ) 空间复杂度为 O(N^2)O(N
     * 2
     *  )。最好情况下，当二叉树为平衡二叉树时，它的高度为 \log NlogN，此时空间复杂度为 O((\log {N})^2)O((logN)
     * 2
     *  )。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        dfs(res,root, "");
        return res;
    }

    public void dfs(List<String> res,TreeNode root,String str){
        if (root !=null) {
            StringBuffer stringBuffer = new StringBuffer(str);
            if (root.left == null && root.right == null) {
                res.add(stringBuffer.append(root.val).toString());
                return;
            }
            stringBuffer.append(root.val).append("->");
            dfs(res, root.left, stringBuffer.toString());
            dfs(res, root.right, stringBuffer.toString());
        }
    }


    /**
     * 们也可以用广度优先搜索来实现。我们维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是叶子节点，则将它对应的路径加入到答案中。如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜索结束，我们即能得到答案。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N^2)O(N
     * 2
     *  )，其中 NN 表示节点数目。分析同方法一。
     * 空间复杂度：O(N^2)O(N
     * 2
     *  )，其中 NN 表示节点数目。在最坏情况下，队列中会存在 NN 个节点，保存字符串的队列中每个节点的最大长度为 NN，故空间复杂度为 O(N^2)O(N
     * 2
     *  )。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode-solution/
     * @param root
     * @return
     */
    public List<String> binaryTreePaths_2(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        if (root == null) {
            return paths;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<String> pathQueue = new LinkedList<String>();

        nodeQueue.offer(root);
        pathQueue.offer(Integer.toString(root.val));

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            String path = pathQueue.poll();

            if (node.left == null && node.right == null) {
                paths.add(path);
            } else {
                if (node.left != null) {
                    nodeQueue.offer(node.left);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
                }

                if (node.right != null) {
                    nodeQueue.offer(node.right);
                    pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
                }
            }
        }
        return paths;
    }

    public List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths_3(TreeNode root) {
        if(root==null) {
            return res;
        }
//        dfs(root,new StringBuilder());
        dfs(root,new StringBuilder(),res);
        return res;
    }

    /**
     * 如果非要借用String的伴随类优化的话，应该把StringBuffer/StringBuilder携带在DFS上下文里。由于可变数组追加/删除元素是O(1)的，在非叶子节点可以获得比较好的性能；而叶子节点上还是会执行O(|s|)的数据拷贝。
     * @param r
     * @param s
     */
    public void dfs(TreeNode r,StringBuilder s){
        if(r==null) {
            return;
        }
        s.append(r.val);
        if(r.left==null && r.right==null){
            res.add(s.toString());
        }
        dfs(r.left,new StringBuilder(s).append("->"));
        dfs(r.right,new StringBuilder(s).append("->"));
    }

    /**
     * 关于时间复杂度。题解中，如果每个节点都进行String的拷贝，那最坏情况出现在退化为链表的树时，这时候由于String长度与节点个数正相关，而每个节点都会进行拷贝，所以渐进复杂度为O(N^2)；
     *
     * 而如果使用可变数组（StringBuilder等），那可以避免非叶子节点的拷贝，这样退化为链表时，时间复杂度反而最好，为O(N)；最坏时间复杂度出现在完全二叉树：叶子节点为N/2个，路径长度为logN，所以时间复杂度为O(N/2 + N/2 * logN) ~ O(NlogN)。
     * 不要用StringBuilder的delete方法，那要走一个数组拷贝动作。用setLength(sz)可以实现同样效果，这个操作在删除尾部的数据时相当于移动内部游标，少一个数组拷贝。
     * @param root
     * @param cur
     * @param paths
     */
    private void dfs(TreeNode root, StringBuilder cur, List<String> paths) {
        if (root == null){
            return;
        }
        if (root.left == null && root.right == null) {
            paths.add(cur.toString() + root.val);
            return;
        }
        int sz = cur.length();
        cur.append(root.val).append("->");
        dfs(root.left, cur,paths);
        dfs(root.right, cur,paths);
//        cur.delete(sz, cur.length());
        cur.setLength(sz);
    }
}
